<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <meta http-equiv="X-UA-Compatible" content="ie=edge">
  <title>Document</title>
</head>
<body>

  <script>
    /*
      冒泡排序
        + 意义: 是把一个乱序的数组通过代码的执行调整成一个有序的数组
    */

    // 准备原始数组
    var arr = [ 9, 1, 2, 3, 4, 5, 6, 7, 8 ] // 目的: [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
    console.log('原始数组 : ', arr)

    /*
      冒泡排序, 是若干数组排序算法的一种

      逻辑:
        1. 遍历数组, 两两对比, 把相对较大的数字向后移动
        2. 遍历一遍以后, 得到的结果就是最大的数字一定在最后面
        3. 重复步骤1, 继续比较, 两轮以后, 最大的两个数字一定在最后两个位置
        4. 不管多少个数字, 只要比较总长度 -1 轮, 那么数组就排序完成了
    */

    // 步骤0: 交换数组内两个位置的数据
    // 借助第三个变量来实现
    // 交换 [0] 和 [1] 位置的数据
    // var tmp = arr[0]
    // arr[0] = arr[1]
    // arr[1] = tmp
    // tmp = null
    // console.log('交换完毕 : ', arr)

    // 步骤1: 遍历数组, 两两比较进行对调
    /*
      假设: 数组的 length === 9
        + 随着遍历, 最后一次一定拿到的
          => 当前是 arr[8]
          => 下一个是 arr[9]
        + 因为 length 是 9, 一定不会有 arr[9] 的数据
          => 我们的最后一次比较是没有意义的
          => 在遍历数组的时候, 少遍历一次就可以了
        + 假设数组 length === 9
          => 值遍历到 8
          => 最后一次的当前: arr[7]
          => 最后一次的下一个: arr[8]
    */
    // for (var i = 0; i < arr.length - 1; i++) {
    //   // 在循环内, i 充当每一个的索引
    //   // 在循环内, arr[i] 就表示当前的每一个数据
    //   // 在循环内, arr[i + 1] 就表示下一个数据
    //   // console.log(arr[i], arr[i + 1])
    //   // 比较进行移动
    //   // console.log('过程 : ', arr[i], ' > ', arr[i + 1], arr[i] > arr[i + 1])
    //   if (arr[i] > arr[i + 1]) {
    //     // 这里的代码执行, 表示当前这个比下一个大
    //     // arr[i] 和 arr[i + 1] 进行数据交换
    //     var tmp = arr[i]
    //     arr[i] = arr[i  + 1]
    //     arr[i + 1] = tmp
    //     tmp = null
    //   }
    // }
    // console.log('一遍以后 : ', arr)


    // 步骤2: 重复执行步骤1, 重复 length - 1 次
    // 遍历数组, 遍历 length - 1 次
    // 在整体比较的过程中, 每一轮减少一次
    // 当 j === 0 的时候, 第 1 轮, 完整比较 8 次   8 - 0
    // 当 j === 1 的时候, 第 2 轮, 完整比较 7 次   8 - 1
    // 当 j === 2 的时候, 第 3 轮, 完整比较 6 次   8 - 2
    // 当 j === 7 的时候, 第 8 轮, 完整比较 1 次   8 - 7
    // for (var j = 0; j < arr.length - 1; j++) {
    //   for (var i = 0; i < arr.length - 1 - j; i++) {
    //     console.log('过程 : ', arr[i], ' > ', arr[i + 1], arr[i] > arr[i + 1])
    //     if (arr[i] > arr[i + 1]) {
    //       var tmp = arr[i]
    //       arr[i] = arr[i  + 1]
    //       arr[i + 1] = tmp
    //       tmp = null
    //     }
    //   }
    //   console.log('一遍以后 : ', arr)

    // }
    // console.log('排序以后以后 : ', arr)




    /*
      一旦有一轮出现全部 false 的情况
        + 从这一轮以后, 就再也不需要比较了
        + 我们只要判断出本轮是不是全 false 就可以了

      问题: 如何判断出本轮全是 false
        + 就看 if 内的代码是否有执行过
        + 因为只有 true 的时候才会执行 if 内的代码
        + 如果这一轮之内, if 内的代码从来没有执行过, 那么就是全 false
        + 在此之后的所有内容都不需要了

      代码:
        + 每一轮开始之前, 假设一个变量, 值为 false
        + 我认为本轮全都是 false, 只要 if 内的代码执行了, 推翻我的假设
    */
    // for (var j = 0; j < arr.length - 1; j++) {

    //   // 每一轮的开始之前, 假设一个变量
    //   var flag = false

    //   for (var i = 0; i <script arr.length - 1 - j; i++) {
    //     console.log('过程 : ', arr[i], ' > ', arr[i + 1], arr[i] > arr[i + 1])
    //     if (arr[i] > arr[i + 1]) {
    //       var tmp = arr[i]
    //       arr[i] = arr[i  + 1]
    //       arr[i + 1] = tmp
    //       tmp = null

    //       // 这里的代码只要执行了, 那么就表示有 true 的, 本轮我的假设不对了
    //       flag = true // 推翻我的假设
    //     }
    //   }

    //   // 一轮完毕以后, 只要 flag 还是 false, 说明本轮没有任何改变
    //   // 从这一轮以后的内容就不需要了
    //   if (!flag) break

    //   console.log('一遍以后 : ', arr)
    // }

    // console.log('最终以后 : ', arr)



    // 冒泡排序
    // 外层循环决定比较多少轮
    for (var i = 0; i < arr.length - 1; i++) {

      // 1. 做假设
      var flag = false

      // 2. 遍历比较
      for (var j = 0; j < arr.length - 1 - i; j++) {
        if (arr[j] > arr[j + 1]) {
          var tmp = arr[j]
          arr[j] = arr[j + 1]
          arr[j + 1] = tmp
          tmp = null

          // 推翻假设
          flag = true
        }
      }

      // 3. 根据假设变量决定是否有后续内容
      if (!flag) break
    }

    console.log('排序之后 : ', arr)
  </script>
</body>
</html>
